package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 113. 路径总和 II
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：[[5,4,11,2],[5,8,4,5]]
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [1,2,3], targetSum = 5
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：root = [1,2], targetSum = 0
 * 输出：[]
 */
public class PathSum1 {

    List<List<Integer>> ans = new ArrayList<>();

    /**
     * 回溯
     *
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        back(root, 0, targetSum, new ArrayList<>());
        return ans;
    }

    public void back(TreeNode root, int sum, int target, List<Integer> list) {
        if (root == null) {
            return;
        }
        sum = sum + root.val;
        list.add(root.val);

        if (sum == target && root.left == null && root.right == null) {
            ans.add(new ArrayList<>(list));
        }
        back(root.left, sum, target, list);
        back(root.right, sum, target, list);

        list.remove(list.size() - 1);
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }
}
